package main

import "fmt"

func main() {
	fmt.Printf("permutations([]int{1, 2, 3}): %v\n", permutations([]int{1, 2, 3, 2}))
}

/**
就是全排列，只不过数组中没有重复数字
*/
func permutations(nums []int) [][]int {
	var ans [][]int
	//dfs(nums, 0, &ans)
	dfs1(nums, 0, &ans)
	return ans
}

func dfs(nums []int, cur int, ans *[][]int) {
	if cur == len(nums) {
		newN := make([]int, len(nums))
		copy(newN, nums)
		*ans = append(*ans, newN)
		return
	}
	// 用原始数组保存结果
	for i := cur; i < len(nums); i++ {
		// 拿2个数来交换位置
		nums[i], nums[cur] = nums[cur], nums[i]
		// 再从下一个数字开始
		dfs(nums, cur+1, ans)
		// 交换回来，为了不影响下一次递归
		nums[i], nums[cur] = nums[cur], nums[i]
	}
}

// 全排列，但是可能有重复数字，要求结果去重

func dfs1(nums []int, cur int, ans *[][]int) {
	if cur == len(nums) {
		newN := make([]int, len(nums))
		copy(newN, nums)
		*ans = append(*ans, newN)
		return
	}
	// 用于保存交换过的数
	set := make(map[int]struct{}, 10)
	// 用原始数组保存结果
	for i := cur; i < len(nums); i++ {
		if _, ok := set[nums[i]]; ok {
			continue
		}
		set[nums[i]] = struct{}{}
		// 拿2个数来交换位置
		nums[i], nums[cur] = nums[cur], nums[i]
		// 再从下一个数字开始
		dfs1(nums, cur+1, ans)
		// 交换回来，为了不影响下一次递归
		nums[i], nums[cur] = nums[cur], nums[i]
	}
}
